package com.zhangxiaofanfan.hotcode.fourth.third;

import java.util.Arrays;

/**
 * <a href="https://leetcode.cn/problems/longest-palindromic-substring/?envType=study-plan-v2&envId=top-100-liked">5. 最长回文子串</a>
 *
 * @date 2024-07-13 03:14:13
 * @author zhangxiaofanfan
 */
public class HotCode093 {
    public static void main(String[] args) {
        HotCode093 hotCode = new HotCode093();
        System.out.println(hotCode.longestPalindrome("babad"));
    }

    public String longestPalindrome(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (boolean[] booleans : dp) {
            Arrays.fill(booleans, true);
        }
        int[] index = {0, 0};
        for (int left = s.length() - 1, right; left >= 0; left--) {
            for (right = left + 1; right < s.length(); right++) {
                dp[left][right] = s.charAt(left) == s.charAt(right) && dp[left + 1][right - 1];
                if (dp[left][right] && (right - left) > (index[1] - index[0])) {
                    index[0] = left;
                    index[1] = right;
                }
            }
        }
        return s.substring(index[0], index[1] + 1);
    }
}